package org.example.myleet.p509;

public class Solution {
    /**
     * O(1)
     * 0 ms
     * 公式法
     * https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
     */
    public int fib(int n) {
        return (int) (1 / Math.sqrt(5.0) * (Math.pow((1 + Math.sqrt(5.0)) / 2, n) - Math.pow((1 - Math.sqrt(5.0)) / 2, n)));
    }
}
